// https://leetcode.cn/problems/is-unique-lcci/

// 题干：实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

// 示例：输入: s = "leetcode"
//       输出: false

// 碎语：int有32位，且每一位要么是0，要么是1，刚好对应有无的两种状态
//       考虑“位图”的思想
//      给一个数n，确定它的二进制表示的第x位是0还是1
//      注意！从右往左位次越来越高
//      (n >> x) & 1

//      将一个数的二进制表示的第x位修改为1
//      n |= (1 << x)

//      将一个数的二进制表示的第x位修改为0
//      n &= (~(1 << x))

//      提取一个数(n)二进制表示中最右侧的1 lowbit
//      n & -n (-n的本质就是按位取反再+1，即将最右侧的1作为分界线，左边的区域全部相反，右边不变)
//      此时再进行按位1与操作，按照有0就是0(此时一定会有0)，这时候就会有0，右边也全部是0
//      仅剩下所要求的1 （00010000）

//      干掉一个数二进制中最右侧的1
//      n & (n - 1) （011010000)
//      减一的本质操作是最右边的1，右侧全部相反，左侧全部不变

//      a ^ 0 = a
//      a ^ a = 0 (消消乐)
//      a^b^c = a^(b^c)
//      证明交换率和结合律
//      异或是无进位相加，本质上是1的抵消

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    bool isUnique(string str)
    {
        int bitMap = 0;

        for (auto ch : str){
            int count = ch - 'a'; // 当前字符对应的二进制位数
            int test = 1 << count;

            if (bitMap & test) return false;
            else bitMap |= test;
        }

        return true;
    }
};

int main()
{
    Solution sol;
    string str = "leetcode";

    cout << sol.isUnique(str) << endl;

    return 0;
}